package nodeList;

public class SequenceLinkImpl implements LinkedList {
    private class Node {
        Object data;
        Node next;//指向Node节点的引用,存放了下一节点的地址

        public Node(Object data, Node next) {
            this.data = data;
            this.next = next;
        }

        public Node(Object data) {
            this.data = data;
        }
    }

    //虚拟头结点，不存储元素，专门作为头结点使用
    //保证任意存放数据都有前驱节点
    private Node dummyHead;//对象只做了声明，此时还没有创建对象，分配地址
    private int size;

    public SequenceLinkImpl() {
        this.dummyHead = new Node(null, null);//new对象，分配地址
    }


    @Override
    public boolean remove(int index) {
        rangeCheck(index);
        Node prev = dummyHead;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        //取得当前节点
        Node cur = node(index);
        prev.next = cur.next;
        //清空当前节点
        cur.next = cur = null;

        return false;
    }

    @Override
    public Object get(int index) {
        rangeCheck(index);
        //取得相应index的Node节点
        Node node = node(index);
        return node.data;
    }

    @Override
    public Object set(int index, Object newData) {
        rangeCheck(index);
        Node node = node(index);
        Object oldData = node.data;
        node.data = newData;
        return oldData;
    }

    @Override
    public boolean contains(Object data) {
        Object[] datas = toArray();
        if(data == null) {
            for(int i = 0;i < datas.length;i++) {
                if(datas[i] == null) {
                    return true;
                }
            }
        }else {
            for(int i = 0;i < datas.length; i++) {
                if(data.equals(datas[i])) {
                    return true;
                }
            }
        }
        return false;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public Object[] toArray() {
        //遍历节点将数据存放到对象数组中
        Object[] datas = new Object[size];
        int i = 0;
        for (Node temp = dummyHead.next; temp != null; temp = temp.next) {
            datas[i++] = temp.data;
        }
        return datas;
    }

    @Override
    public void clear() {
        for (Node node = dummyHead.next; node != null; node = node.next) {
            node.data = null;
            Node temp = node.next;
            node.next = null;
            node = temp;
            size--;
        }
    }

    @Override
    public void add(Object data) {
        addLast(data);
    }

    //任意位置插入元素
    private void add(int index, Object data) {
        rangeCheck(index);
        Node prev = dummyHead;//TODO
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
//        Node newNode = new Node(data,prev.next);
        Node newNode = new Node(data);
        newNode.next = prev.next;//null.next
        prev.next = newNode;
        size++;
    }

    private void addFirst(Object data) {
        add(0, data);
    }

    private void addLast(Object data) {
        add(size, data);
    }

    //判断index是否合法
    private void rangeCheck(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("Illegal index!!!");
        }
    }

    private Node node(int index) {
        Node cur = dummyHead.next;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        return cur;
    }
}
